// https://leetcode.com/problems/longest-common-prefix/

// Write a function to find the longest common prefix string amongst an array of strings.
// 编写一个函数以在字符串数组中找到最长的公共前缀字符串。如果没有公共前缀，则返回一个空字符串“

/**
 * 解题思路
 * 1、找出关键字 “公共字符串”，也就是只要有一个满足，所有都满足
 * 2、将数组的第一个元素作为基准，（判空）将它转化为数组
 * 3、遍历数组，取出的每个字符和下标去匹配所有数组字符（不能使用 filter 方法，因为它有可能跳过字符）
 * 4、返回过滤的字符

 * 注意点：1、判空；2、使用every
 */

/**
 * @param {string[]} strs
 * @return {string}
 */
function longestCommonPrefix (strs) {
  const firstBase = strs && strs.shift()
  const str = []

  firstBase && firstBase.split('').every((item, index) => {
    const flag = strs.every(value => value.charAt(index) === item)
    if (flag) {
      str.push(item)
    }
    return flag
  })

  return str.join('')
}

// 代码优化, 遍历字符串，拿到的每一个字符去和数组的所有元素的相同位置比较, 不匹配跳出循环
function longestCommonPrefix1 (strs) {
  if (!strs || !strs.length) {
    return ''
  }
  const firstItem = strs[0]
  let str = ''

  for (const key in firstItem) {
    const flag = strs.every(item => {
      return firstItem[key] === item[key]
    })

    if (flag) {
      str += firstItem[key]
    } else {
      break
    }
  }

  return str
}

// 代码优化 2 使用 indexOf 技巧 0 的特殊位置

function longestCommonPrefix2 (strs) {
  if (!strs || !strs.length) {
    return ''
  }

  const first = strs.shift()
  let prefix = ''

  for (const key of first) {
    const flag = strs.every(item => (!item.indexOf(prefix + key)))

    if (flag) {
      prefix += key
    } else {
      break
    }
  }

  return prefix
}

// 方法2 使用正则解法

function longestCommonPrefixRegexp (strs) {
  let res = ''
  if (!strs || !strs.length) {
    return res
  }

  const first = strs.shift()

  for (const index in first) {
    const prefix = first.substr(0, Number(index) + 1)
    const regexp = new RegExp(`^${prefix}`) // 关键步骤
 
    if (!(strs.every(item => regexp.test(item)))) {
      break
    }
    res = prefix
  }

  return res
}

const arr = ['flower', 'flow', 'flight']

console.log(longestCommonPrefixRegexp(arr))

module.exports = {
  longestCommonPrefix,
  longestCommonPrefix1,
  longestCommonPrefix2,
  longestCommonPrefixRegexp
}
